package algorithm.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author apple
 * 动态规划
 **/

public class DynamicProgramming {


    /**
     * MxN矩阵 矩阵最小路径和
     * 最小路径和 dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+arr[i][j]
     * 最大路径和 dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1])+arr[i][j]
     **/
    public static int minMatrix(int[][] arr) {
        /**行数**/
        int m = arr.length;
        /**列数**/
        int n = arr[0].length;
        if (m <= 0 || n <= 0) {
            return 0;
        }
        /**根据原始矩阵的大小初始化结果矩阵**/
        int[][] dp = getInts(arr, m, n);
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }


    /**
     * 矩阵最大路径和
     **/
    public static int maxMatrix(int[][] arr) {
        int[][] dp = initDp(arr);
        int m = arr.length;
        int n = arr[0].length;
        if (m <= 0 || n <= 0) {
            return 0;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + arr[i][j];
            }
        }
        return dp[m - 1][n - 1];
    }


    /**
     * 初始化二维数组
     **/
    private static int[][] initDp(int[][] arr) {
        int m = arr.length;
        int n = arr[0].length;
        if (m <= 0 || n <= 0) {
            return new int[0][0];
        }
        int[][] dp = getInts(arr, m, n);
        return dp;
    }

    /**
     * 根据原始矩阵的大小初始化结果矩阵 dp[][]
     **/
    private static int[][] getInts(int[][] arr, int m, int n) {
        int[][] dp = new int[m][n];
        /**第一行第一列初始化**/
        dp[0][0] = arr[0][0];
        /**初始化第一列，不含第一行**/
        for (int i = 1; i < m; i++) {
            dp[i][0] = dp[i - 1][0] + arr[i][0];
        }
        /**初始化第一列，不含第一列**/
        for (int i = 1; i < n; i++) {
            dp[0][i] = dp[0][i - 1] + arr[0][i];
        }
        return dp;
    }

    /**
     * 三角形数组计算
     * 最小路径和 dp[i][j]=Math.min(dp[i+1][j],dp[i+1][j+1])+row.get(i)
     * 最大路径和 dp[i][j]=Math.max(dp[i+1][j],dp[i+1][j+1])+row.get(i)
     **/
    public static int fixTriangleTotal(List<List<Integer>> triangle) {
        /**三角形的高度**/
        int height = triangle.size();
        int[][] dp = new int[height][height];
        /**三角形最后一行的数值**/
        List<Integer> lastRow = triangle.get(height - 1);
        for (int i = 0; i < height; i++) {
            dp[height - 1][i] = lastRow.get(i);
        }
        /**从下往上数第二行开始计算**/
        for (int i = height - 2; i >= 0; --i) {
            List<Integer> row = triangle.get(i);
            for (int j = 0; j < i + 1; ++j) {
                dp[i][j] = Math.max(dp[i + 1][j], dp[i + 1][j + 1]) + row.get(j);
            }
        }
        return dp[0][0];
    }

    /**
     * 给定一个无序的整数数组，找到其中最长上升子序列的长度
     * 输入: [1,10,9,2,5,3,7,101,18]
     * 输出: 4
     * 解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4
     **/
    public static int longestSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        /**初始化dp[]**/
        int[] dp = new int[nums.length];
        /**数组全部填充1**/
        Arrays.fill(dp, 1);
        /**最长子序列的长度**/
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[j] + 1, dp[i]);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }


    /**
     * 最大子段和
     * N个整数组成的序列a[1],a[2],a[3],…,a[n]，求该序列如a[i]+a[i+1]+…+a[j]的连续子段和的最大值。
     * 当所给的整数均为负数时和为0。
     * 例如：-2, 11, -4, 13, -5, 192，和最大的子段为：11, -4, 13, -5, 192。和为207。
     ***/
    public static int maxSubArraySum(int[] a) {
        int maxSum = 0;
        int currentSum = 0;
        for (int i = 0; i < a.length; i++) {
            currentSum = currentSum + a[i];
            if (currentSum > maxSum) {
                //更新最大子段和
                maxSum = currentSum;
            }
            //当前累加和为负数时舍弃，重置为0
            if (currentSum < 0) {
                currentSum = 0;
            }
        }
        return maxSum;
    }

    public static void main(String[] args) {
        /**最大子段和**/
        System.out.println("最大子段和");
        int[] a = {-2, 11, -4, 13, -5, 192};
        System.out.println(maxSubArraySum(a));

        /**最长上升子序列的长度**/
        System.out.println("最长上升子序列的长度");
        int[] nums = {10, 1, 2, 10, 3, 6, 4, 7, 11};
        System.out.println(longestSubArray(nums));


        /**  MxN矩阵 矩阵最小路径和    ;**/
        System.out.println("MxN矩阵 矩阵最小路径和");
        int[][] arr = {{3, 1, 1},
                {4, 4, 1},
                {1, 3, 2},
                {4, 5, 3}};
        System.out.println(minMatrix(arr));
/**        System.out.println(maxMatrix(arr));**/


        /**三角形数组最大(最小)路径和计算**/
        System.out.println("三角形数组计算");
        List<Integer> list1 = Arrays.asList(1, 0, 0);
        List<Integer> list2 = Arrays.asList(1, 4, 0);
        List<Integer> list3 = Arrays.asList(1, 5, 6);
        List<Integer> list4 = Arrays.asList(4, 9, 6, 7);
        List<List<Integer>> totalList = new ArrayList<>();
        totalList.add(list1);
        totalList.add(list2);
        totalList.add(list3);
        totalList.add(list4);
        System.out.println(fixTriangleTotal(totalList));
    }
}
